package com.xsherl.leetcode.solution;

import cn.hutool.core.lang.Assert;
import com.xsherl.leetcode.utils.ArrayUtils;
import com.xsherl.leetcode.utils.PrintUtils;

public class ValidSudoku {

    /**
     * 利用位图来存储行、列、小宫格内出现的数字
     *
     * @param board
     * board.length == 9
     * board[i].length == 9
     * board[i][j] 是一位数字或者 '.'
     */
    public boolean isValidSudoku(char[][] board) {
        int[] rows = new int[9];
        int[] cols = new int[9];
        int[] boxs = new int[9];
        for (int i = 0; i < 9; ++i){
            for (int j = 0; j < 9; ++j){
                char c = board[i][j];
                if (c == '.'){
                    continue;
                }
                int n = 1 << (c - '0');
                if ((rows[i] & n) != 0){
                    return false;
                }
                rows[i] |= n;
                if ((cols[j] & n) != 0){
                    return false;
                }
                cols[j] |= n;
                int boxNumber = (i / 3) * 3 + (j / 3);
                if ((boxs[boxNumber] & n) != 0){
                    return false;
                }
                boxs[boxNumber] |= n;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] board = ArrayUtils.parseArray("" +
                "[[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"]\n" +
                ",[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"]\n" +
                ",[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"]\n" +
                ",[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"]\n" +
                ",[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"]\n" +
                ",[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"]\n" +
                ",[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"]\n" +
                ",[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"]\n" +
                ",[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n" +
                "", char[].class);
        PrintUtils.println(board);
        boolean validSudoku = new ValidSudoku().isValidSudoku(board);
        System.out.println(validSudoku);
        Assert.isTrue(validSudoku);
    }

}
